from functools import cache


class Solution:
    def findIntegers(self, n: int) -> int:

        size = n.bit_length()

        @cache
        def f(index, limit, last, flag):
            if index == -1:
                return flag
            t = n >> index & 1
            r = t if limit else 1
            ans = 0
            for i in range(r + 1):
                ans += f(index - 1, limit and i == t, i, flag or last == 1 and i == 1)
            return ans

        return n + 1 - f(size - 1, True, 0, False)


s = Solution()
print(s.findIntegers(5))


class Solution:
    def findIntegers(self, n: int) -> int:
        dp = [0] * 31
        dp[0] = 1
        dp[1] = 1
        for i in range(2, 31):
            dp[i] = dp[i - 1] + dp[i - 2]

        pre = 0
        res = 0

        for i in range(29, -1, -1):
            val = (1 << i)
            if n & val:
                res += dp[i + 1]
                if pre == 1:
                    break
                pre = 1
            else:
                pre = 0

            if i == 0:
                res += 1

        return res

# 作者：力扣官方题解
# 链接：https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/solutions/990719/bu-han-lian-xu-1de-fei-fu-zheng-shu-by-l-9l86/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。